package 回溯;

import java.util.ArrayDeque;
import java.util.Deque;

//https://leetcode.cn/problems/max-area-of-island/
/*
求每个岛的长在比较最大，不要往复杂想
 */
public class 岛屿的最大面积 {
    int[] x = new int[]{-1, 0, 0, 1};
    int[] y = new int[]{0, -1, 1, 0};
    int n = 0;

    public int maxAreaOfIsland(int[][] grid) {
        int m = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    m = Math.max(m, fun_DFS(grid, i, j));
                    // m = Math.max(m, fun_BFS(grid, i, j)); BFS操作
                }
            }
        }
        return m;
    }

    public int fun_DFS(int[][] grid, int gx, int gy) {
        if (gx >= 0 && gx < grid.length && gy >= 0 && gy < grid[0].length && grid[gx][gy] == 1) {
            grid[gx][gy] = 2;
            return 1 + fun_DFS(grid, gx - 1, gy) + fun_DFS(grid, gx + 1, gy) + fun_DFS(grid, gx, gy - 1) + fun_DFS(grid, gx, gy + 1);
        }
        return 0;
    }
    public int fun_BFS(int[][] grid, int gx, int gy) {
        int n = 0;
        Deque<Point> que = new ArrayDeque<>();
        que.offer(new Point(gx, gy));
        grid[gx][gy] = 2;//入队就操作
        while (!que.isEmpty()) {
            Point point = que.poll();
            n++;
            grid[point.x][point.y] = 2;
            for (int i = 0; i < 4; i++) {
                int nx = point.x + x[i];
                int ny = point.y + y[i];
                if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && grid[nx][ny] == 1) {
                    que.offer(new Point(nx, ny));
                    grid[nx][ny] = 2;//入队时候就将点制为2（操作过）否则对角线位置会重复判断
                }
            }
        }
        return n;
    }
    //辅助BFS的点类
    public class Point{
        int x;
        int y;

        public Point() {
        }
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

}
